package fileReader.demo.reader;

import java.util.Vector;



/**
 * The main methods to execute Dijkstras algorithm are implemented here.
 */

public class Dijkstra
{
	/**
	 * Constructor for the class Dijkstra.
	 * @param cvisibilitygraph Object from the visibilitygraph.
	 * Adds elements into a remaining vector vertexes from visibilitygraph.
	 * @param cvertex Object from vertex
	 */
    public Dijkstra(VisibilityGraph cvisibilitygraph, Vertex cvertex)
    {
    	int i = cvisibilitygraph.numVerts();
    	//Vector with initially all the vertex
        Remaining = new Vector(i);
        for(int j = 0; j < i; j++)
            Remaining.addElement(cvisibilitygraph.vertexAt(j));
        //Reset cost --> cost= infinity and predecesor= null
        cvisibilitygraph.ResetCosts();
        //First vertex cost = 0
        cvertex.setCost(0.0D);
    }

   /**
    *  Dijkstra's Algorithm itself! Calculates shortest paths.
    */
        
    public void ComputeAllShortestPaths()
    {
      while(!Remaining.isEmpty()) 
        {
    	  	//extract least weight node 
            Vertex closest_node = ExtractClosestNode();

            //extract list with adjacent edges from this node
            Vector adj_edges = closest_node.getAdj();
            
            for(int i = 0; i < adj_edges.size(); i++)
            {
            	//extract edge
                Edge edge = (Edge)adj_edges.elementAt(i);
                //get opposite node
                Vertex opposite_node = edge.getOpposite(closest_node);
                //calculate new cost to the opposite node
                //and assign its predecessor
                relax(closest_node, opposite_node, edge);
            }

        }
    }

    /**
     * Cheks which node is the closest. This is called from the method
     * ComputeAllShortestPaths().
     * @return closestnode node that is the closest
     */
    private Vertex ExtractClosestNode()
    {
        int i_closestnode = -1;
        double d = 1.7976931348623157E+308D; //infinity
        int remaining_nodes = Remaining.size();
        
        //scan remaining nodes and get that one with the least cost
        for(int k = 0; k < remaining_nodes; k++)
            if(((Vertex)Remaining.elementAt(k)).getCost()< d)
            {
                d = ((Vertex)Remaining.elementAt(k)).getCost();
                i_closestnode = k;
            }

        Vertex closestnode = (Vertex)Remaining.elementAt(i_closestnode);
        //delete from remaining list
        Remaining.removeElementAt(i_closestnode);
        return closestnode;
    }

    /**
     * This method calculates a new cost to the opposite node
     * and assign its predecessor. This is called from the method
     * ComputeAllShortestPaths().
     * @param closest_node 
     * @param opposite_node
     * @param cedge
     */
    private void relax(Vertex closest_node, Vertex opposite_node, Edge cedge)
    {
    	// node cost + edge weigth
        double d = closest_node.getCost() + cedge.getCost();
        
        if(opposite_node.getCost() > d)
        {
            opposite_node.setCost(d);
            opposite_node.setPredecessor(closest_node);
        }
    }
    
    /**
     * This method calculates the shortest path length. ??
     * @param cvertex vertex
     * @return path that is shortest.
     */
    public Path ShortestPathTo(Vertex cvertex)
    {
        Path path = new Path();
        path.setCost(cvertex.getCost());
        // dijkstra is already computed
        // we travel across the precedessors to get the path
        
        //the last node won't have predecessor --> cvertex==null
        for(; cvertex != null; cvertex = cvertex.getPredecessor())
        	path.getVertexList().add(cvertex);
        return path;
    }
    
    //Nodes that are remaining in the path
    private Vector Remaining;
}